package com.since.algorithm.arrys;

import java.util.Arrays;

/**
 * Created by Sincerity on 2020/5/6.
 * 描述： 数组相关的算法
 * 1. 寻找数组的中心索引算法{@link #pivotIndex(int[])}
 * 2. 至少是其他数字两倍的最大数{@link #dominantIndex(int[])}
 * 3. +1算法 {@link #plusOne(int[])}
 * 4. 寻找数组中二个数相加等于目标值得索引位置 {@link #twoSum(int[], int)}
 */
public class ArraysAlgorithm {
    public static void main(String[] args) {
        int[] num = {1, 5, 8, 6};
        ArraysAlgorithm algorithm = new ArraysAlgorithm();
        System.out.println(Arrays.toString(algorithm.twoSum(num, 7)));
    }

    /**
     * 求数组中二个元素位置相加的目标值
     *
     * @param nums   目标数组
     * @param target 二个数组索引的和
     * @return 这个数组中的位置
     */
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[]{i, j};
                }
            }
        }

        return null;
    }

    /**
     * ＋1算法
     * 思路 给数组的最后一个位置+1 来判断最后一个位置是否等于0
     * 如果等于0就再给最后位置-1的位置+1 判断是否为0 依次类推
     * 如果数组中的数+1都为0的话新建一个原数组长度+1的新生数组并且把第0位变成1即可
     *
     * @param digits 数组
     * @return 返回＋1的数组
     */
    public int[] plusOne(int[] digits) {
        //倒序去遍历数组
        for (int i = digits.length - 1; i >= 0; i--) {
            //当前位置的元素=当前位置元素+1跟10取模
            System.out.println("-----" + digits[i]);
            digits[i] = ++digits[i] % 10;
            System.out.println(digits[i]);
            if (digits[i] != 0) {
                return digits;
            }
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }

    /**
     * 寻找数组的中心索引算法
     *
     * @param nums 数组
     * @return 返回中心索引 存在返回索引 不存在返回*1
     */
    private int pivotIndex(int[] nums) {
        int sum = 0, left = 0;
        for (int num : nums) {
            //得到数组的总和
            sum += num;
        }
        for (int i = 0; i < nums.length; i++) {
            //左边元素==元素总和-当前元素时 返回当前索引
            if (left << 1 == sum - nums[i]) return i;
            //左边的元素相加值
            left += nums[i];
        }
        return -1;
    }

    /**
     * 至少是其他数字两倍的最大数
     * 思路 先找到最大数 和 第二大的数 如果第二大的数满足时最大数的二倍即存在这个索引
     *
     * @param nums 数组
     * @return 查找数组中的最大元素是否至少是数组中每个其他数字的两倍.
     * 如果是，则返回最大元素的索引，否则返回-1。
     */
    private int dominantIndex(int[] nums) {
        int max = -1, secondMax = -1, index = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                //保存上一次遍历的最大值
                secondMax = max;
                //得到数组中的最大数
                max = nums[i];
                //纪录最大数的索引
                index = i;
                //当前的数大于第二大数并且当前数不等于最大数的时候给第二大数重新赋值
            }
            if (nums[i] > secondMax && nums[i] != max) {
                //得到第二大的数
                secondMax = nums[i];
            }
        }
        if (secondMax * 2 <= max) {
            return index;
        } else {
            return -1;
        }

    }
}
